{ Statement: http://informatics.mccme.ru/moodle/mod/statements/view3.php?chapterid=182
  Verdict: Accepted
}
uses
	SysUtils, Math;
 
const
	MAXN = 110;
	INF = round(1e9);
 
type
	edge = record
		a, b, cost : longint;
	end;
 
var   
	i, n, m : longint;
	p : array[0..MAXN] of longint;
	e : array[0..1000010] of edge;
 
procedure BellmanFord(v, t : longint);
 
var
	i, j : longint;
	d : array[0..MAXN] of longint;
 
begin
	for i := 1 to MAXN do
		d[i] := INF;
	fillchar(p, sizeof(p), -1);
	d[v] := 0;
	for i := 1 to n do begin
		for j := 1 to m do
			if (d[e[j].a] < INF) and (d[e[j].b] > d[e[j].a] + e[j].cost) then begin
				d[e[j].b] := d[e[j].a] + e[j].cost;
				p[e[j].b] := e[j].a;
			end;
	end;
end;
 
begin
	reset(input,'input.txt');
	rewrite(output,'output.txt');
	read(n, m);
	for i := 1 to m do begin
		read(e[i].a, e[i].b);
		e[i + m].a := e[i].b;
		e[i + m].b := e[i].a;
		e[i + m].cost := 1;
		e[i].cost := 1;
	end;
	m := m shl 1;
	BellmanFord(1, n);
	for i := 2 to n do begin
		assert(p[i] <> -1);
		writeln(p[i], ' ', i);
	end;
end.